home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 167_01 / fgrep.doc < prev    next >
Text File  |  1985-08-19  |  28KB  |  739 lines
  1. /* 
  2. HEADER:     CUG
  3. TITLE:        Parallel Pattern Matching and FGREP
  4. VERSION:    1.00
  5. DATE:        09/20/85
  6. DESCRIPTION:    "Development of algorithm used in FGREP, a full
  7.         emulation of Unix's 'fgrep' utility."
  8. KEYWORDS:    fgrep, grep, filter, UNIX, pattern-matching
  9. SYSTEM:
  10. FILENAME:    FGREP.DOC
  11. WARNINGS:
  12. CRC:        xxxx
  13. SEE-ALSO:    FGREP.C
  14. AUTHORS:    Ian Ashdown - byHeart Software
  15. COMPILERS:
  16. REFERENCES:    AUTHORS: Bell Telephone Laboratories;
  17.         TITLE:     UNIX Programmer's Manual Vol. 1, p. 166;
  18.         AUTHORS: A.V. Aho & M.J. Corasick;
  19.         TITLE:     'Efficient String Matching: An Aid to
  20.              Bibliographic Search'
  21.              Communications of the ACM
  22.              pp. 333 - 340, Vol. 18 No. 6 (June '75);
  23. ENDREF
  24. */
  25.  
  26. /*-------------------------------------------------------------*/
  27.  
  28. Ian Ashdown
  29. byHeart Software
  30. 1089 West 21st Street
  31. North Vancouver
  32. British Columbia V7P 2C6
  33. Canada
  34.  
  35. Date: April 12th, 1985
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.            Parallel Pattern Matching and FGREP
  46.            -----------------------------------
  47.  
  48.              by Ian Ashdown
  49.             byHeart Software
  50.  
  51. *****************************************************************
  52. *                                *
  53. * NOTE: This manuscript was published in the September 1985    *
  54. *    issue of Doctor Dobb's Journal. It may be reproduced    *
  55. *    for personal, non-commercial use only, provided that    *
  56. *    the above copyright notice is included in all copies.    *
  57. *    Copying for any other use without previously obtaining    *
  58. *    the written permission of the author is prohibited.    *
  59. *                                *
  60. *****************************************************************
  61.  
  62.  
  63.  
  64.     Preparing an index to a large technical book. Finding all
  65. references to a person in several years' worth of a company's
  66. minutes of meetings. Searching for all occurrences of a specific
  67. sequence of events in the volumes of data obtained from a
  68. scientific experiment. All of these problems and many more are
  69. examples of searching for patterns in a set of data. The question
  70. is, what is the most efficient search algorithm to use?
  71.  
  72.     For single patterns, such as searching for the phrase
  73. "binary tree" in a text file, there are two of particular
  74. interest: the Boyer-Moore Algorithm (reference 5) and the
  75. Knuth-Morris-Pratt Algorithm (reference 6). Both are fast and
  76. reasonably simple to implement. However, neither is appropriate
  77. when more than one pattern at a time must be searched for.
  78.  
  79.     One algorithm that is appropriate can be found in a paper
  80. published in the June '75 issue of "Communications of the ACM"
  81. (reference 1). Entitled "Efficient String Matching: An Aid to
  82. Bibliographic Search" and written by Alfred Aho and Margaret
  83. Corasick of Bell Laboratories, the paper presents "a simple and
  84. efficient algorithm to locate all occurrences of any of a finite
  85. number of keywords in a string of text". Without modification to
  86. the algorithm, a "keyword" can be taken to mean any pattern, and
  87. "a string of text" to mean any sequence of symbols, be it ASCII
  88. text, digitized data obtained from a video camera, or whatever.
  89.  
  90.     The algorithm has some interesting features. For
  91. instance, most pattern matching schemes must employ some form of
  92. backtracking, or rescanning of the string when an attempted match
  93. to a pattern fails or multiple patterns are to be matched. The
  94. Aho-Corasick algorithm differs in that it searches for all of the
  95. patterns in parallel. By doing so, it can process the string in
  96. one pass without any backtracking.
  97.  
  98.     The algorithm also recognizes patterns that overlap in
  99. the string. For example, if the patterns are "he", "she" and
  100. "hers", the algorithm will correctly identify matches to all
  101. three in the string "ushers".
  102.  
  103.     As to speed of execution, it is independent of the number
  104. of patterns to be matched! This perhaps surprising feature is a
  105. direct result of the patterns being searched for in parallel.
  106.  
  107.     Curiously, this algorithm has all but disappeared from
  108. the literature of computer science. Of the hundreds of textbooks
  109. and articles written since that discuss pattern matching, only a
  110. few reference the paper, and none that I know of present the
  111. Aho-Corasick algorithm itself. Unless you have access to back
  112. issues of "Communications of the ACM", you will likely never
  113. encounter it.
  114.  
  115.     On the other hand, if you work with UNIX you may have
  116. used a utility based on the algorithm: "fgrep". This useful tool
  117. searches for and displays all occurrences of a set of keywords
  118. and phrases in one or more text files. While it does not accept
  119. wildcard characters in its patterns like UNIX's more flexible
  120. "grep" utility, it does illustrate the speed of the Aho-Corasick
  121. algorithm in comparison with other pattern matching methods.
  122. Typically, "fgrep" is five to ten times faster than "grep" in
  123. searching files for fixed string patterns.
  124.  
  125.     Given its general usefulness, I thought it appropriate to
  126. reintroduce Aho and Corasick's work in this article. At the same
  127. time, it seemed a shame that "fgrep" has been restricted to the
  128. UNIX operating system. Therefore, the source code in C for a full
  129. implementation (reference 4) of "fgrep" has been included. This
  130. serves not only to demonstrate the algorithm, but also to bring
  131. the idea of a public domain UNIX one small step closer to
  132. reality.
  133.  
  134. Inside The Machine
  135. ------------------
  136.  
  137.     The Aho-Corasick algorithm consists of two phases:
  138. building a "finite state automaton" (FSA for short), then running
  139. a string of data through it, with each consecutive symbol being
  140. considered a separate input. Before analyzing these phases, a
  141. quick summary of what finite state automata are and how they work
  142. is in order. (For a more detailed discussion, reference 2 is
  143. recommended.)
  144.  
  145.     In essence, an FSA is a conceptual machine that can be in
  146. any one of a finite number of "states". It also has a set of
  147. "state transition" rules and a set of "inputs", which together
  148. with the set of states define what inputs cause the machine to
  149. change from one state to another. Finally, since a machine serves
  150. no purpose without producing some output, an FSA has one or more
  151. "terminal" states. Output is produced only when the FSA enters
  152. such states. 
  153.  
  154.     A physical example of an FSA could be a light switch.
  155. This device has two states, ON and OFF. Its inputs consist of
  156. someone pushing the switch UP or DOWN. ON is a terminal state,
  157. where the associated lamp produces visible radiation. The state
  158. transition rules can be stated in a simple truth table:
  159.  
  160.         +------------------+
  161.         |    | OFF  |  ON  |
  162.         |----|------|------|
  163.         | UP | ON   |  --  |
  164.         |DOWN| --   |  OFF |
  165.         +------------------+
  166.  
  167.     Alternatively, this could be shown as a "state transition
  168. diagram":
  169.              DOWN
  170.            +-------------+
  171.            |         |
  172.            V         |
  173.         +-----+  UP   ******
  174.         +-->| OFF |------>* ON *<---+
  175.         |     +-----+       ******    | 
  176.         |      |         |      |
  177.         | DOWN |         |  UP  |
  178.         +------+         +------+
  179.  
  180. where no state transition on a particular input (as shown in the
  181. truth table) is equivalent to a transition from a state to itself
  182. (as shown in the diagram).
  183.  
  184.     Getting ahead of ourselves for a moment, look at Figure
  185. 1a, which shows part of an FSA (the other parts are shown in
  186. Figures 1b and 1c, and will be explained shortly). By having
  187. sequences of states, it is possible for the FSA to recognize
  188. patterns in an input stream. For example, presenting the string
  189. "she" to the FSA shown in Figure 1a would cause it to change from
  190. State 0 to States 3, 4 and 5 as each input symbol of the string
  191. is processed. State 5 is a terminal state that indicates the
  192. pattern "she" was recognized.
  193.  
  194.     There are two types of FSA that can be built, one
  195. "nondeterministic" (Algorithm 1) and the other "deterministic"
  196. (Algorithm 2). The nondeterministic one (NFSA for short) uses
  197. functions called "go_to", "failure" and "output", while the
  198. deterministic FSA (DFSA) uses "move" and "output". The difference
  199. between the two is that while the NFSA can make one or more state
  200. transitions per input symbol, the DFSA makes only one. With fewer
  201. transitions to make, a DFSA can process its input in less time
  202. than an equivalent NFSA.
  203.  
  204.     The "go_to" function accepts as input parameters the
  205. current state of th